//给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。 
//
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。 
//
// 
// 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abc"
//输出：7
//解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
// 
//
// 示例 2： 
//
// 
//输入：s = "aba"
//输出：6
//解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
// 
//
// 示例 3： 
//
// 
//输入：s = "aaa"
//输出：3
//解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 2000 
// s 仅由小写英文字母组成 
// 
//
// 
// Related Topics字符串 | 动态规划 
//
// 👍 164, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class DistinctSubsequencesIi {
    public static void main(String[] args) {
        Solution solution = new DistinctSubsequencesIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int distinctSubseqII(String s) {
            int n = s.length(), MOD = (int) 1e9 + 7;
            int[] dp = new int[n];  // 索引i出现的子序列的个数
            Arrays.fill(dp, 1);

            int[] last = new int[26]; // 保存前面字符出现的位置
            Arrays.fill(last, -1);

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 26; j++) {
                    // 如果出现过
                    if (last[j] != -1) {
                        dp[i] = (dp[i] + dp[last[j]]) % MOD;
                    }
                }
                // 更新
                last[s.charAt(i) - 'a'] = i;
            }

            int ans = 0;
            for (int i = 0; i < 26; i++) {
                if (last[i] != -1) {
                    ans = (ans + dp[last[i]]) % MOD;
                }
            }

            return ans;
        }*/

        // 优化
        public int distinctSubseqII(String s) {
            int n = s.length(), MOD = (int) 1e9 + 7;
            // dp[k]表示dp[last[j]]，但此时初始值设置为0，相加的时候也不会改变
            int[] dp = new int[26];
            for (int i = 0; i < n; i++) {
                int total = 1;
                for (int j = 0; j < 26; j++) {
                    total = (total + dp[j]) % MOD;
                }
                dp[s.charAt(i) - 'a'] = total;
            }

            int ans = 0;
            for (int i = 0; i < 26; i++) {
                if (dp[i] != -1) {
                    ans = (ans + dp[i]) % MOD;
                }
            }

            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
